<?php
/**
 * 有虚拟头结点的单链表
 * 与没有虚拟头结点的单链表相比，优点是添加、删除操作可以不用单独判断头结点是否为空。
 * 类似于循环队列多申请一个空间，用来判断是否队列未满的做法。
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbLinkedListInterface;

class VirSingleLinkedList implements XxbLinkedListInterface
{
    /**
     * 虚拟头结点
     * @var LinkedListNode
     */
    private $virtualHead;

    /**
     * 结点的个数
     * @var
     */
    private $size;

    public function __construct()
    {
        $this->virtualHead = new LinkedListNode();
        $this->size = 0;
    }

    /**
     * 翻转链表：
     * 遍历链表，把当前遍历的结点作为新链表的头结点即可。
     */
    public function reverse()
    {
        $newVirtualHead = new LinkedListNode();
        $cursor = $this->virtualHead->getNext();
        while (!is_null($cursor)) {
            // 注意原链表的遍历不能中断
            $preNode = $cursor;
            $cursor = $cursor->getNext();
            // 设置当前结点成为新链表头结点
            $preNode->setNext($newVirtualHead->getNext());
            $newVirtualHead->setNext($preNode);
        }
        $this->virtualHead = $newVirtualHead;
    }

    public function isEmpty()
    {
        return $this->size == 0;
    }

    /**
     * @param $index
     * @param $value
     */
    public function add($index, $value)
    {
        if ($index < 0 || $index > $this->size) {
            throw new \InvalidArgumentException('lined list add error, illegal index.');
        }
        for ($i=0, $cursor=$this->virtualHead; $i<$index; $i++) {
            $cursor = $cursor->getNext();
        }
        $cursor->setNext(new LinkedListNode($value, $cursor->getNext()));
        $this->size++;
    }

    public function unshift($value)
    {
        $this->add(0, $value);
    }

    public function push($value)
    {
        $this->add($this->size, $value);
    }

    public function offsetUnset($index)
    {
        // TODO: Implement offsetUnset() method.
    }

    public function pop()
    {
        // TODO: Implement pop() method.
    }

    public function shift()
    {
        // TODO: Implement shift() method.
    }

    public function unsetVal($value)
    {
        // TODO: Implement unsetVal() method.
    }

    public function offsetSet($index, $value)
    {
        // TODO: Implement offsetSet() method.
    }

    public function valueOffsetGet($value)
    {
        // TODO: Implement valueOffsetGet() method.
    }

    public function valueExists($value)
    {
        // TODO: Implement valueExists() method.
    }

    public function offsetGet($index)
    {
        // TODO: Implement offsetGet() method.
    }

    public function bottom()
    {
        // TODO: Implement bottom() method.
    }

    public function top()
    {
        // TODO: Implement top() method.
    }

    public function count()
    {
        // TODO: Implement count() method.
    }

    public function __toString()
    {
        $str = 'linked list: head[';
        for ($i=0, $cursor=$this->virtualHead; $i<$this->size; $i++) {
            $cursor = $cursor->getNext();
            $str .= $cursor->getValue() . '->';
        }
        return trim($str, '->') . ']';
    }
}
